package oj;

public class LC124 {
    int maxSum=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;

    }
    //函数语义：返回给父节点 子节点所能提供的最大贡献
    private int dfs(TreeNode root){
        if(root==null) return 0;
        //计算左子节点的最大贡献
        int left=Math.max(dfs(root.left),0);
        //计算右节点的最大贡献
        int right=Math.max(dfs(root.right),0);

        //计算当前根节点的内部路径的值，并挑战最大值
        maxSum=Math.max(maxSum,(root.val+left+right));

        //计算当前节点返回给父节点的最大贡献
        int max=Math.max(left,right)+root.val;

        return max;

    }
}
